﻿//class MinStack {
//public:
//    void push(int val) {
//        s.push(val);
//        v.push_back(val);
//    }
//    void pop() {
//        s.pop();
//        v.pop_back();
//    }
//    int top() {
//        return s.top();
//    }
//    int getMin() {
//        int Min = v[v.size() - 1];
//        for (int i = v.size() - 2; i >= 0; i--) {
//            if (Min > v[i]) {
//                Min = v[i];
//            }
//        }
//        return Min;
//    }
//private:
//    stack<int> s;
//    vector<int> v;
//};

//class Solution {
//public:
//    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
//        if (pushV.size() != popV.size()) {
//            return false;
//        }
//        int x = 0;
//        for (int i = 0; i < pushV.size(); i++) {
//            x ^= pushV[i];
//            x ^= popV[i];
//        }
//        if (x != 0) {
//            return false;
//        }
//        stack<int> s;
//        vector<int>::iterator pushit = pushV.begin();
//        vector<int>::iterator popit = popV.begin();
//        while (pushit != pushV.end()) {
//            s.push(*pushit);
//            pushit++;
//            while (!s.empty() && s.top() == *popit) {
//                s.pop();
//                popit++;
//            }
//        }
//        if (s.empty()) {
//            return true;
//        }
//        return false;
//    }
//};

//本题要考虑负数的情况
//#include <iostream>
//#include <vector>
//#include <string>
//#include <stack>
//using namespace std;
//class Solution {
//public:
//    int evalRPN(vector<string>& tokens) {
//        stack<int> s;
//        for (int i = 0; i < tokens.size(); i++) {
//            string str = tokens[i];
//            int right = 0, left = 0;
//            if (str.back() != '+' && str.back() != '-' && str.back() != '*' &&
//                str.back() != '/') {
//                s.push(stoi(str));
//            }
//            else {
//                switch (str[0]) {
//                case '+':
//                    right = s.top();
//                    s.pop();
//                    left = s.top();
//                    s.pop();
//                    s.push(left + right);
//                    break;
//                case '-':
//                    right = s.top();
//                    s.pop();
//                    left = s.top();
//                    s.pop();
//                    s.push(left - right);
//                    break;
//                case '*':
//                    right = s.top();
//                    s.pop();
//                    left = s.top();
//                    s.pop();
//                    s.push(left * right);
//                    break;
//                case '/':
//                    right = s.top();
//                    s.pop();
//                    left = s.top();
//                    s.pop();
//                    s.push(left / right);
//                    break;
//                }
//            }
//        }
//        return s.top();
//    }
//};
//int main()
//{
//    vector<string> v; //["2","1","+","3","*"]
//    v.push_back("2");
//    v.push_back("1");
//    v.push_back("+");
//    v.push_back("3");
//    v.push_back("*");
//    Solution S;
//    int x = S.evalRPN(v);
//    cout << x;
//    return 0;
//}